Finite State Machines (FSMs), also known as finite automata, depict behavioral models composed of inputs, states, transitions, and outputs (or actions). Two well known finite state machine types are Moore and Mealy FSMs. In Moore machines the output depends on state, whereas in Mealy machines the output depends on transition. In practice, many FSMs employ both types of machines in combination. These FSM abstractions were described by their namesakes in the late 1950's and have been widely utilized in a variety of fields (mathematics, logic, linguistics, computer science, etc.) for the past half century. Other FSMs have also been described, as have methods to transform one type into another.
Specified FSMs can be classified into two groups: recognizers and transducers. Recognizers produce binary output: yes/true (recognized) or no/false (not recognized). Transducers generate output based on input and/or current state and are often used to control applications. Transducers transform (or map) ordered sets of input events into corresponding ordered sets of output events.
FSMs are used with some regularity to control computer systems and applications, both in hardware and software. In many applications, the specified FSMs are hard-wired or hard-coded, as the case may be, into the system or application. In general, the FSM is developed based upon a specific application, and methods or systems are required to provide for the creation or development of the FSM in accordance with the application requirements. Some customizable general purpose FSMs have been devised to aide in the development of control mechanisms for computer systems and applications.
An example of a system and method for implementing a FSM based upon configuration data is disclosed in U.S. Pat. No. 7,039,893. A FSM Engine is used to generate specific configurations for different state machines based on configuration data using a common method. This common configuration structure is used for all state machine implementations, and changes in the state machine design drive changes in the configuration data instead of in executable software. Multiple software state machines are thus implemented using a configurable approach. In addition, state machine processing is performed periodically and state transition events are handled without the need for an event driven operating system. The disclosed approach, however, has several deficiencies. For example, a new FSM is needed for each instance, and customized executable code, e.g., as described in the preferred embodiment the “configuration data” are C language code and header files, is produced from the FSM model. In addition, a new production-compilation-deployment cycle is needed to incorporate FSM model changes into running systems.
An alternative approach utilized web services-business process execution language (WS-BPEL) that provides both externalization and an execution engine. However, WS-BPEL does not enforce FSM control flows. Therefore, WS-BPEL flows can be written that do not conform to any FSM Specification. Another disadvantage of WS-BPEL is that there are no guarantees to model the entire flow, e.g. all states and state transitions, thus failing to provide any level of assurance or provability.
Expressing an FSM externally as Extensible Markup Language (XML) is also well known in the Artificial Intelligence (AI) and computer gaming literature (see for example http://www.igda.org/ai/report-2004/fsm.html or http://www.codeproject.com/csharp/xmlfsm.asp). These externally specified FSMs have not separated execution from state maintenance.
More generally, FSMs have been defined using state tables as in “The Virtual Finite State Machine Implementation Paradigm” (see http://www.lucent.com/minds/techjournal/pdf/winter—97/paper08.pdf). Again, these techniques have been used to generate customized code.
The prior art does not teach how to employ an externally defined FSM for flow control such that changes can be implemented during runtime “on the fly”.